/*
 * @lc app=leetcode id=75 lang=cpp
 *
 * [75] Sort Colors
 */
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        if (len < 1) {
            return ;
        }

        sortColors(nums, 0, 0);
        int i=0;
        while(i<len && nums[i]==0)
            i++;

        sortColors(nums, i, 1);
    }

    void sortColors(vector<int>& nums, int st, int target) {
        int len = nums.size();
        int i = st;
        int j = len-1;

        while(i < j) {
            while(i<len && nums[i] == target)
                i++;
            while(j>=0 && nums[j] != target) 
                j--;
            if (i < j) {
                std::swap(nums[i], nums[j]);
                i++;
                j--;
            }
        }
    }
};

